// 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include<bits/stdc++.h>
using namespace std;

// 模拟二叉搜索树，递归
// 左边自底向上向右
// 向上比小，向右必大

// 执行用时：
// 20 ms
// , 在所有 C++ 提交中击败了
// 88.03%
// 的用户
// 内存消耗：
// 12.8 MB
// , 在所有 C++ 提交中击败了
// 9.73%
// 的用户


class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int hang = matrix.size();
        if(hang ==0){
            return false;
        }
        int lie = matrix[0].size();
        if(lie==0){
            return false;
        }

        int x=hang-1;
        int y=0;
        bool res = false;
        while(true){
            if(matrix[x][y]==target){
                res =true;
                break;
            }
            else if(matrix[x][y]>target){
                --x;
            }
            else{
                ++y;
            }
            if(x<0 || y>=lie){
                break;
            }
        }
        return res;
    }
};